#include "LinkList.h"

void InitLinkList(Llist *list)
{
    list->head = (node *)malloc(sizeof(node));
    if (list->head == NULL)
    {
        printf("InitLinkList error!\n");
        return;
    }
    list->head->value = 0;
    list->head->next = NULL;
    list->len = 0;
}

node* CreateNode(ElementType element)
{
    node *newNode = (node *)malloc(sizeof(node));
    if (newNode == NULL)
    {
        printf("InitLinkList error!\n");
        return NULL;
    }
    newNode->value = element;
    newNode->next = NULL;
    return newNode;
}

bool InsertLinkTail(Llist *list, ElementType element)
{
    node *newNode = CreateNode(element);
    if (newNode == NULL)
    {
        return false;
    }
    node* travalPoint = list->head;
    while (travalPoint->next != NULL)
    {
        travalPoint = travalPoint->next;
    }
    travalPoint->next = newNode;
    list->len++;
    
    return true;
}

void TravelLinkList(Llist *list)
{
    printf("list len: %d\n", list->len);
    node* travalPoint = list->head->next;
    while (travalPoint != NULL)
    {
        printf("%d ", travalPoint->value);
        travalPoint = travalPoint->next;
    }
    printf("\n");
}

bool InsertHead(Llist *list, ElementType element)
{
    node *newNode = CreateNode(element);
    if (newNode == NULL)
    {
        return false;
    }
    newNode->next = list->head->next;
    list->head->next = newNode;
    list->len++;
    return true;
}

bool InsertByIndex(Llist *list, int index, ElementType element)
{
    if (index < 0 || index > list->len)
    {
        printf("illigel index\n");
        return false;
    }
    node *travalPoint = list->head;
    node *newNode = CreateNode(element);
    if (newNode == NULL)
    {
        return false;
    }
    for (int i = 0; i < index; i++)
    {
        travalPoint = travalPoint->next;
    }
    newNode->next = travalPoint->next;
    travalPoint->next = newNode;
    list->len++;
    return true;
}

bool RemoveByIndex(Llist *list, int index)
{
    if (index < 0 || index >= list->len)
    {
        printf("illigel index\n");
        return false;
    }
    node *travalPoint = list->head;
    for (int i = 0; i < index; i++)
    {
        travalPoint = travalPoint->next;
    }
    node *freeNode = travalPoint->next;
    travalPoint->next = freeNode->next;
    list->len--;
    free(freeNode);
    return true;
}

bool RemoveByElement(Llist *list, ElementType element)
{
    node *travalPoint = list->head;
    for (int i = 0; i < list->len; i++)
    {
        if (travalPoint->next->value == element)
        {
            RemoveByIndex(list, i);
            i--;
        }
        else
        {
            travalPoint = travalPoint->next;
        }
    }
    return true;
}

bool UpdateByIndex(Llist *list, int index, ElementType element)
{
    if (index < 0 || index >= list->len)
    {
        printf("illigel index\n");
        return false;
    }
    node *travalPoint = list->head->next;
    for (int i = 0; i < index; i++)
    {
        travalPoint = travalPoint->next;
    }
    travalPoint->value = element;
    return true;
}

bool UpdateByElement(Llist *list, ElementType oldValue, ElementType newValue)
{
    node *travalPoint = list->head->next;
    for (int i = 0; i < list->len; i++)
    {
        if (travalPoint->value == oldValue)
        {
            travalPoint->value = newValue;
        }
        travalPoint = travalPoint->next;
    }
    return true;
}

ElementType* FindElementByIndex(Llist *list, int index)
{
    if (index < 0 || index >= list->len)
    {
        printf("illigel index\n");
        return NULL;
        
    }
    node *travalPoint = list->head->next;
    for (int i = 0; i < index; i++)
    {
        travalPoint = travalPoint->next;
    }
    return &travalPoint->value;
}

int *FindElementByValue(Llist *list, ElementType element)
{
    int *arr = (int *)malloc(sizeof(int) * (list->len + 1));
    if (arr == NULL)
    {
        printf("FindElementByValue malloc error\n");
        return NULL;
    }
    int k = 0;
    node *travalPoint = list->head->next;
    for (int i = 0; i < list->len; i++)
    {
        if (travalPoint->value == element)
        {
            arr[k++] = i;
        }
        travalPoint = travalPoint->next;
    }
    arr[k] = -1;
    return arr;
}

bool IsHaveElement(Llist *list, ElementType element)
{
    int *a = FindElementByValue(list, element);
    if (a == NULL)
    {
        return false;
    }
    if (a[0] == -1)
    {
        free(a);
        return false;
    }
    else
    {
        free(a);
        return true;
    }
}

bool IsEmpty(Llist *list)
{
    return !list->len;
}

void BubbleSort(Llist *list)
{
    for (int i = 0; i < list->len-1; i++)
    {
        node *travalPoint = list->head;
        for (int j = 0; j < list->len-i-1; j++)
        {
            if (travalPoint->next->value > travalPoint->next->next->value)
            {
                node* prev = travalPoint->next;
                node* back = prev->next;
                prev->next = back->next;
                back->next = prev;
                travalPoint->next = back;
            }
            travalPoint = travalPoint->next;
        }
    }
}

Llist GetInsection(Llist *list1, Llist *list2)
{
    Llist insection;
    InitLinkList(&insection);
    for (int i = 0; i < list1->len; i++)
    {
        for (int j = 0; j < list2->len; j++)
        {
            if (*FindElementByIndex(list1, i) == *FindElementByIndex(list2, j))
            {
                int value = *FindElementByIndex(list1, i);
                int *a = FindElementByValue(&insection, value);
                if (a == NULL)
                {
                    continue;
                }
                if (a[0] == -1)
                {
                    InsertLinkTail(&insection, value);
                }
                free(a);
            }
        }
    }

    return insection;
}

void Deduplicate(Llist *list)
{
    BubbleSort(list);
    for (int i = 1; i < list->len; i++)
    {
        if (*FindElementByIndex(list, i) == *FindElementByIndex(list, i-1))
        {
            RemoveByIndex(list, i);
            i--;
        }
    }
}

Llist GetUnionSet(Llist *list1, Llist *list2)
{
    Llist unionSet;
    InitLinkList(&unionSet);

    for (int i = 0; i < list1->len; i++)
    {
        InsertLinkTail(&unionSet, *FindElementByIndex(list1, i));
    }
    for (int i = 0; i < list2->len; i++)
    {
        InsertLinkTail(&unionSet, *FindElementByIndex(list2, i));
    }
    Deduplicate(&unionSet);
    return unionSet;
}

Llist Merge(Llist *list1, Llist *list2)
{
    Llist list3;
    InitLinkList(&list3);
    BubbleSort(list1);
    BubbleSort(list2);
    // int i = 0;
    // int j = 0;
    // while (i < list1->len && j < list2->len)
    // {
    //     if (*FindElementByIndex(list1, i) < *FindElementByIndex(list2, j))
    //     {
    //         InsertLinkTail(&list3, *FindElementByIndex(list1, i));
    //         i++;
    //     }
    //     else
    //     {
    //         InsertLinkTail(&list3, *FindElementByIndex(list2, j));
    //         j++;
    //     }
    // }
    // for (int k = i; k < list1->len; k++)
    // {
    //     InsertLinkTail(&list3, *FindElementByIndex(list1, k));
    // }
    // for (int k = j; k < list2->len; k++)
    // {
    //     InsertLinkTail(&list3, *FindElementByIndex(list2, k));
    // }

    node *p1 = list1->head->next;
    node *p2 = list2->head->next;

    while (p1 != NULL && p2 != NULL)
    {
        if (p1->value <= p2->value)
        {
            InsertLinkTail(&list3, p1->value);
            p1 = p1->next;
        }
        else
        {
            InsertLinkTail(&list3, p2->value);
            p2 = p2->next;
        }
    }
    while (p1 != NULL)
    {
        InsertLinkTail(&list3, p1->value);
        p1 = p1->next;
    }
    while (p2 != NULL)
    {
        InsertLinkTail(&list3, p2->value);
        p2 = p2->next;
    }
    
    return list3;
}

void Reserve(Llist *list)
{
    if (list->len <= 1)
    {
        return;
    }
    node *prev = NULL;
    node *cur = list->head->next;
    node *next = cur->next;
    while (next != NULL)
    {
        cur->next = prev;
        prev = cur;
        cur = next;
        next = cur->next;
    }
    cur->next = prev;
    list->head = cur;
}

node* ReserveRecursive(node *n)
{
    // 这个节点是尾巴
    if (n->next == NULL)
    {
        //尾巴需要返回
        return n;
    }
    else
    {
        //递归寻找尾巴
        node *tail = ReserveRecursive(n->next);
        n->next->next = n;
        // 为了第一层存在的，要将原先的头，后来的尾巴next指针置为空
        n->next = NULL;
        // 把尾巴继续往上一层传
        return tail;
    }
}

void FreeLinkList(Llist *list)
{
    while (list->head != NULL)
    {
        node *next = list->head->next;
        free(list->head);
        list->head = next;
    }
    list->len = 0;
}
